- 论文原文：Exploring Evolution of Dynamic Networks via Diachronic Node Embeddings
- 作者：Jin Xu, Yubo Tao, Yuyu Yan, and Hai Lin
- 发表刊物/会议：2018 TVCG
文章提出了一种利用graph embedding的方法来探索动态图的方法。
一般而言，传统的动态图可视化方法可以分成三大类，基于动画的方法（animation），基于时间轴的方法（timeline），以及其他方法（如投影 projection）。基于动画的方法，往往会高亮相邻两帧之间的变化，但是当时间比较长的时候无法追踪变化；基于时间轴的方法，则将所有内容一起显示在同个视图中，但空间是个问题；基于投影的方法，把每一帧当做一个点，用投影的方法投影在一个视图中，但是很难展现图的结构的信息；
文章提出了一种同时展示结构属性和动态属性的可视分析方法。具体步骤如下：
A生成动态图，B为动态图每一帧的每个节点生成embedding向量，C将这些embedding向量对齐到同一向量空间中，DEF利用embedding向量可以做的数据挖掘（节点分类，节点聚类，动态轨迹聚类），G可视交互分析；
文章的主要贡献有：
- 提出了一种新的节点embedding的方法
- 提出了两种基于节点embedding的动态图聚类方法
- 一个可视分析交互系统
动态图的构建
首先，将动态图按照$\Delta t$的时间间隔，划分成多个时间片段，然后将$[t_i-\omega/2, t_i+\omega/2)$作为$t_i$时刻对应的动态图。
节点embedding向量的生成
文章利用了skip-gram模型为单帧图的每一个节点生成embedding向量；
skip-gram模型可以理解为，当你输入一系列句子（sentences），以及包含这些句子中的词的语料库（corpus），skip-gram模型会为你预测语料库中的单词出现在某个指定的单词（word）附近的概率；这个过程中，会有一个重要的产物，叫做词向量，利用两个词向量的内积，我们就可以看到两个词在句子中共同出现的概率有多高；
skip-gram模型的目标函数，可以看做在最大化，同个句子中的相邻词汇的词向量的内积。
文章同样利用了skip-gram模型，做了如下修改：
用节点（node）替代词（word），用路径（path）替代句子（sentence），用节点集合（nodes set）代替语料库（corpus），于是也可以产生节点向量。
值得注意的有：
path的生成，靠的是random walk，假如图是一个有权图（weighted），那么random walk也需要依赖边权重。并且，为了提高效率，文章使用了负采样。
skip-gram模型的目标函数的修改。这里不仅仅要使得同一路径上的节点出现概率高，还要使得不相邻的节点共同出现的概率低：
将上一帧产生的embedding向量，传入下一帧的skip-gram模型中，用以保持两帧之间的连续性：
embedding向量对齐
为了使得所有的embedding向量能够对齐到同一个向量空间中，方便比较和计算。所以这一步要对embedding向量进行正交变换，使得下面这个矩阵范数最小（也即差异最小）：
$$
\left|M_{i} \Omega-M_{b}\right|_{F}
$$
其中$M_i$表示第$i$帧的向量构成的矩阵（$n \times d$）；$\Omega$指的是正交变换矩阵；$M_b$指的是基准矩阵，也就是所有embedding向量都要对齐到这个基准矩阵上来；$\left|*\right|_{F}$则是Frobenius矩阵范数。
关于$M_b$的选取，有三种不同的方法：
- 对齐到节点数最多的一帧（适合于变化较小的动态图）
- 对齐到前一帧（因为两帧之间的变化不大，所以误差会较小，但是不断对齐的过程中，误差就会累计）
- 将所有帧分成好几段，每一段都对齐到其中的某一帧（解决了上面的问题）
节点分类和聚类
节点的分类：
根据前后两帧之间节点embedding的变化，可以判断这个节点是dynamic（动态）还是stable（稳定）。
当前后两帧的节点之间的欧氏距离（文中叫做evolution value）,大于阈值$\theta$时，则认为其为dynamic；
节点聚类：
可以用于揭示某一段时间内，稳定的社团结构。文章提出了稳定的概念，也就是大部分节点在这段时间内维持一个stable的状态。那么，在一段稳定时间内，将同一节点不同时间的所有向量求均值，就作为这段时间内该节点的向量。然后利用这些节点进行k-means聚类，即可得到不同的聚类（社团）。
趋势聚类：
如何对节点随时间变化的趋势进行聚类。两个节点随时间演化产生的两条轨迹，可以利用如下方法判断距离：
同一时刻，两个节点的向量求欧氏距离；所有时刻的所有欧氏距离的平均值，作为两条轨迹的距离。
利用knn graph，就可以对这些轨迹进行聚类。
系统界面
文章提出五个分析目标：
- 整体网络的演化分析
- 动态节点的演化分析
- 动态社团的时序分析
- 稳定社团的结构分析
- 将分析与网络的整体进行关联
分析系统的视图与这五个目标对应：
控制面板（A）
统计视图（B）
对应目标1
横轴表示时间，纵轴表示网络的平均演变值（evolution value），用以刻画网络的整体趋势；其中的统计直方图分别用红、绿、紫分别表示动态节点数量，新出现节点数量和消失的节点数量。
节点视图（D）
对应目标2
横轴表示时间，纵轴则表示节点的演变值从低到高。只展示动态的节点，并且用黄到红的颜色映射来表示节点的演变值。
趋势视图（C）
对应目标3
横轴：时间；纵轴：利用PCA，将节点向量投影至1维，并用线连起来。可以看到很多不同的社团演化，其中比较特殊的有如下：
结构视图（E）
对应目标4
用PCA按照节点向量，投影至二维。
灰色表示稳定的节点，并且用大小来表示稳定的持续时间；动态节点则用了粉色-绿色的颜色映射来展示演变值。凸包围盒则用以概括不同的社团。
snapshot视图（F）
对应目标5
将以往探索过的结构记录在最右方。